# 66/100 二分查找-搜索旋转排序数组(好题)
# leetcode第33题: https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/2/5
from leetcode import test


def search(nums: list[int], target: int) -> int:
    """
    nums[k], -----, nums[n], nums[0] ------- nums[k-1]
    """
    n = len(nums)
    l, r = 0, n - 1
    while l <= r:
        mid = ((r - l) >> 1) + l
        if target == nums[mid]:
            return mid
        elif nums[0] <= nums[mid]:
            if nums[0] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:
            if nums[mid] < target <= nums[n - 1]:
                l = mid + 1
            else:
                r = mid - 1
    return -1


if __name__ == '__main__':
    inp = [{"nums": [4, 5, 6, 7, 0, 1, 2], "target": 0},
           {"nums": [4, 5, 6, 7, 0, 1, 2], "target": 3},
           {"nums": [4, 5, 6, 7, 8, 0, 1, 2], "target": 0},
           {"nums": [4, 5, 6, 7, 8, 0, 1, 2], "target": 5},
           {"nums": [6, 7, 8, 0, 1, 2, 3, 4, 5], "target": 5},
           {"nums": [1], "target": 0},
           ]
    out = [4, -1, 5, 1, 8, -1]
    test.test_function(search, inp, out)
